// https://leetcode.cn/problems/maximum-strictly-increasing-cells-in-a-matrix/description/?envType=daily-question&envId=2024-06-19
class Solution {
public:
    int maxIncreasingCells(vector<vector<int>>& mat) {
        int m = mat.size(), n = mat[0].size();
        map<int,vector<pair<int,int>>> g;
        for(int i = 0; i<m;i++){
            for (int j = 0; j < n; j++) {
                g[mat[i][j]].emplace_back(i, j);
            }
        }
        vector<int> row_max(m),col_max(n);
        for(auto & [_,pos] : g){        // 从小到大
            vector<int> mx;
            for (auto& [i, j] : pos) {  
                mx.push_back(max(row_max[i], col_max[j]) + 1);      // mx存i,j位置所能对应的最大值
            }
            for (int k = 0; k < pos.size(); k++) {
                auto& [i, j] = pos[k];
                row_max[i] = max(row_max[i], mx[k]); // 更新第 i 行的最大 f 值
                col_max[j] = max(col_max[j], mx[k]); // 更新第 j 列的最大 f 值
            }
        }
        return ranges::max(row_max);
    }
};

unsigned long  size1;
//unsigned long size2;
//long long fun(int x, int y, vector<vector<long long>>& dfs,
//	vector<vector<int>>& mat) {
//	size1 = mat.size();
//	size2 = mat[0].size();
//	if (dfs[x][y] != 0) {
//		return dfs[x][y];
//	}
//	else {
//		long long tmp = 0;
//		long long r = -1;
//		for (int i = 0; i < size1; i++) {
//			if (mat[i][y] > mat[x][y])
//				//tmp = max(tmp,fun(i,y,dfs,mat));
//			{
//				if (r == -1 || mat[r][y] < mat[i][y])
//					r = i;
//			}
//		}
//		if(r!=-1)
//			tmp = max(tmp, fun(r, y, dfs, mat));
//		r = -1;
//		for (int i = 0; i < size2; i++) {
//			if (mat[x][i] > mat[x][y])
//				//tmp = max(tmp,fun(x,i,dfs,mat));
//			{
//				if (r == -1 || mat[x][r] < mat[x][i])
//					r = i;
//			}
//		}
//		if (r != -1)
//			tmp = max(tmp, fun(x, r, dfs, mat));
//		dfs[x][y] = tmp + 1;
//		return tmp + 1;
//	}
//}
//class Solution {
//public:
//	int maxIncreasingCells(vector<vector<int>>& mat) {
//		size1 = mat.size();
//		size2 = mat[0].size();
//		vector<vector<long long>> dfs = { size1,vector<long long>(size2,0) };
//		long long ret = 0;
//		for (int i = 0; i < size1; i++) {
//			for (int j = 0; j < size2; j++) {
//				long long t = fun(i, j, dfs, mat);
//				ret = max(ret, t);
//				//cout<<t <<' ';
//			}
//			//cout<<endl;
//		}
//		return ret;
//	}
//};
//int main() {
//	vector<vector<int>> mm = { {3,1},{3,4} };
//	Solution().maxIncreasingCells(mm);
//}